from collections import Counter
from typing import List


class Node:
    def __init__(self, name, source):
        self.name = name  # 当前文件夹名称
        self.source = source  # 文件夹上层路径名称
        self.children = []  # 所有子结点列表
        self.code = ""

    def __repr__(self):
        return self.source + self.name


class Solution:
    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:
        # 时间复杂度：O(NlogN)
        paths.sort(key=lambda x: (len(x), x))

        # 构造树结构
        root = Node("", "")
        nodes_mapping = {"": root}
        for path in paths:
            source = ".".join(path[:-1])
            name = path[-1]

            now_node = Node(name, source)

            nodes_mapping[source].children.append(now_node)

            if source != "":
                nodes_mapping[source + "." + name] = now_node
            else:
                nodes_mapping[name] = now_node

        # 排序所有结点的子结点列表
        for now_node in nodes_mapping.values():
            now_node.children.sort(key=lambda x: x.name)
            # print(now_node.source, now_node.name, now_node.children)

        # 遍历所有结点寻找结构相同的文件夹
        count = Counter()

        def dfs1(node):
            if not node.children:
                return node.name

            children = []
            for child in node.children:
                children.append(dfs1(child))
            res = "(" + ".".join(children) + ")"
            count[res] += 1
            node.code = res
            return node.name + res

        dfs1(root)

        for now_node in nodes_mapping.values():
            print(now_node.source, now_node.name, now_node.code)

        # 遍历移除所有需要删除的文件夹
        ans = []

        def dfs2(node):
            if node.children:
                # 当前结点是需要被移除的结点
                if count[node.code] > 1:
                    return

            # 如果当前结点不是根结点，则将没有被移除的结点添加到返回结果中
            if node.name != "":
                if node.source != "":
                    ans.append(node.source.split(".") + [node.name])
                else:
                    ans.append([node.name])

            for child in node.children:
                dfs2(child)

        dfs2(root)

        return ans


if __name__ == "__main__":
    # [["d"],["d","a"]]
    print(Solution().deleteDuplicateFolder(paths=[["a"], ["c"], ["d"], ["a", "b"], ["c", "b"], ["d", "a"]]))

    # [["c"],["c","b"],["a"],["a","b"]]
    print(Solution().deleteDuplicateFolder(
        paths=[["a"], ["c"], ["a", "b"], ["c", "b"], ["a", "b", "x"], ["a", "b", "x", "y"], ["w"], ["w", "y"]]))

    # [["c"],["c","d"],["a"],["a","b"]]
    print(Solution().deleteDuplicateFolder(paths=[["a", "b"], ["c", "d"], ["c"], ["a"]]))

    # []
    print(Solution().deleteDuplicateFolder(
        paths=[["a"], ["a", "x"], ["a", "x", "y"], ["a", "z"], ["b"], ["b", "x"], ["b", "x", "y"], ["b", "z"]]))

    # [["b"],["b","w"],["b","z"],["a"],["a","z"]]
    print(Solution().deleteDuplicateFolder(
        paths=[["a"], ["a", "x"], ["a", "x", "y"], ["a", "z"], ["b"], ["b", "x"], ["b", "x", "y"], ["b", "z"],
               ["b", "w"]]))
